package com.wjy.Data_Structure.sort.sort3;

import java.util.Arrays;

import com.wjy.Data_Structure.sort.DataWrap;

//直接插入排序
public class InsertSort {
	public static void insertSort(DataWrap[] data) {
		System.out.println("开始排序：\n");
		int arrayLength = data.length;
		for (int i = 1; i < arrayLength; i++) {
			//当整体后移时，保证data[i]的值不会丢失
			DataWrap tmp = data[i];
			if (data[i].compareTo(data[i - 1]) < 0) {
				int j = i - 1;
				//整体后移一格
				for (; j >= 0 && data[j].compareTo(tmp) > 0; j--) {
					data[j + 1] = data[j];
				}
				data[j + 1] = tmp;
			}
			System.out.println(Arrays.toString(data));

		}
	}

	public static void main(String[] arys) {
		DataWrap[] data = { new DataWrap(21, ""), new DataWrap(30, ""), new DataWrap(49, ""), new DataWrap(30, ""),
				new DataWrap(16, ""), new DataWrap(9, ""), };
		System.out.println("排序之前：\n" + Arrays.toString(data));
		insertSort(data);
		System.out.println("排序之后：\n" + Arrays.toString(data));
	}
}
